package Stack;

import java.util.Stack;

/**
 *  题目 ： 使用两个栈，实现队列
 *  题目详解 ：
 *  用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，
 *  分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead操作返回 -1 )
 */
public class TwoStackToQueue {
    /**
     *  核心思想 ：
     *  （1）使用输入栈来存储所输入的元素（模拟队列尾部插入元素）
     *  （2）为实现队列的头部元素弹出（先进先出的功能），需要使用输出栈将输入栈中的元素逆序过来，从而能够更好地模拟队列的先进先出原理
     *  （3）为保证队列元素的顺序，尤其仅当输出栈中元素为空时，才将输入栈中的元素弹出并且压入输出栈中
     */
    // 输入栈（模拟队列尾部元素的插入）
    // 输出栈（模拟队列头部元素的删除）
    Stack<Integer> inStack;
    Stack<Integer> outStack;
    public TwoStackToQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    public void appendTail(int value) {
        //此处不需要进行判断，由于直接在输入栈中接受输入元素即可
//        System.out.println(value);
        inStack.push(value);
    }

    public int deleteHead() {
        /**
         *  （1）当输出栈不为空时，直接将outStack栈中栈顶元素弹出；
         *  （2）当输出栈为空时，需要将输入栈中的元素压入输出栈中；
         *  特殊情况 ：
         *  当输出栈为空时，同时输入栈也为空，此时需要返回-1；
         */
        if(outStack.isEmpty()){
            if(inStack.isEmpty()){
                return -1;
            }
            // 在输出栈为空，并且同一时间输入栈不为空时，需要将输入栈中的所有元素弹出并且压入输出栈中
            while(!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }
}
